#include <stdio.h>
#include <stdlib.h>

// 链表节点结构
struct LNode
{
  int val;
  struct LNode *next;
};

// 查找并返回链表的中间节点（偶数个节点时返回第一个中间节点）
struct LNode *FindMiddleElement1(struct LNode *head)
{
  // 使用快慢指针法
  struct LNode *slow = head;
  struct LNode *fast = head;

  // 快指针每次走两步，慢指针每次走一步
  while (fast->next != NULL && fast->next->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;
  }

  // 当快指针到达末尾时，慢指针正好指向中间节点
  // 对于偶数个节点，slow指向第一个中间节点
  return slow;
}

// 查找并返回链表的中间节点（偶数个节点时返回第二个中间节点）
struct LNode *FindMiddleElement2(struct LNode *head)
{
  // 使用快慢指针法
  struct LNode *slow = head;
  struct LNode *fast = head;

  // 快指针每次走两步，慢指针每次走一步
  while (fast != NULL && fast->next != NULL)
  {
    slow = slow->next;
    fast = fast->next->next;
  }

  // 当快指针到达末尾时，慢指针正好指向中间节点
  // 对于偶数个节点，slow指向第二个中间节点
  return slow;
}

// 创建新节点
struct LNode *createNode(int val)
{
  struct LNode *node = (struct LNode *)malloc(sizeof(struct LNode));
  node->val = val;
  node->next = NULL;
  return node;
}

// 打印链表
void printList(struct LNode *head)
{
  struct LNode *current = head;
  while (current != NULL)
  {
    printf("%d ", current->val);
    current = current->next;
  }
  printf("\n");
}

// 主函数用于测试
int main()
{
  // 创建链表 10 -> 20 -> 30 -> 40 -> 50 -> 60
  struct LNode *head = createNode(10);
  head->next = createNode(20);
  head->next->next = createNode(30);
  head->next->next->next = createNode(40);
  head->next->next->next->next = createNode(50);
  head->next->next->next->next->next = createNode(60);

  printf("链表元素为: ");
  printList(head);

  // 获取中间节点
  struct LNode *mid1 = FindMiddleElement1(head);
  struct LNode *mid2 = FindMiddleElement2(head);

  printf("偶数个元素取第一个元素为: %d\n", mid1->val);
  printf("偶数个元素取第二个元素为: %d\n", mid2->val);

  return 0;
}